/*
 * @lc app=leetcode.cn id=1287 lang=typescript
 *
 * [1287] 有序数组中出现次数超过25%的元素
 */

// @lc code=start
function findSpecialInteger(arr: number[]): number {
    const limit = Math.ceil(arr.length / 4);
    let temp: number;
    const cache = new Map<number, number>();
    for (let i = 0; i < arr.length; i++) {
        const element = arr[i];
        const count = (cache.get(element) || 0) + 1;
        // 超过 25% ， 这题目有歧义，
        if (count === limit) temp = element;
        if (count > limit) return element;
        cache.set(element, count);
    }
    return temp!;
}
// @lc code=end
